Corelab Seminar
2011-2012
Alexandros Aggelopoulos (NTUA)
On aspects of layered graph drawing
Abstract.
Motivated from rules and directives of Air Traffic, we consider airports and direct-to routes as a Graph along with a specific geometric embedding
(working terminology is "Traffic Graph"), and thus lead to aspects of Layered Graph Drawing. We present the concepts of planar decomposition
and graph thickness θ(n), geometric thickness θ(n) and book thikness bt(n), explaining the inequality θ(n)<=θ(n)<=bt(n) and results
in what regards their asymptotic behaviour.
Discussing their application to our model, we first focus on complete Traffic Graphs, categorize them as convex and non-convex, and we determine
some lower and upper bounds on the their number of layers, giving a first main result. We then set a bunch of questions and problems for further investigation..